package FINAL.xd_tap_C;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import FINAL.find_rumors.Calculaotr_distance;

public class GSSS {

	public static void main(String[] args) {
		int[][] matrix = new int[10][10];
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				matrix[i][j] = -1;
			}
		}
		matrix[0][1] = 1;
		matrix[1][2] = 1;
		matrix[1][3] = 1;
		matrix[3][4] = 1;
		matrix[4][5] = 1;
		matrix[4][6] = 1;
		matrix[6][7] = 1;
		matrix[7][8] = 1;
		matrix[8][9] = 1;

		int[] M = new int[10];
		for (int i = 0; i < 10; i++) {
			M[i] = i;
		}

		List<Integer> kq = C(matrix, M);
		for (int i = 0; i < kq.size(); i++) {
			System.out.print("\nKQ: " + kq.get(i));
		}
	}

	/**
	 * 
	 * @param matrix
	 *            ma trận biểu diễn đồ thị
	 * @param M
	 *            Tập node giám sát dương
	 * @return tập nguồn hợp lệ C
	 */
	public static List<Integer> C(int[][] matrix, int[] M) {
		int gioi_han_kc = 200;
		int size = matrix.length;
		List<Integer> C = new ArrayList<Integer>();
		//
		List<Integer> Monitor = new ArrayList<Integer>();
		for (int i = 0; i < M.length; i++) {
			Monitor.add(M[i]);

		}
		//
		int[][] Pm = new int[size][size];
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				Pm[i][j] = -1;
			}
		}
		//
		int[][] Sm = new int[size][size];

		for (int i = 0; i < Monitor.size(); i++) {
			for (int j = 0; j < size; j++) {
				Sm[Monitor.get(i)][j] = -1;
			}
		}
		System.out.println("Khởi tạo Sm");
		// Xác định các tập Sm: tập các node có đường đi đến m
		for (int i = 0; i < Monitor.size(); i++) {
			// Xác định tập Si là tập node có đường đi đến node i:
			int index = 0;
			for (int j = 0; j < size; j++) {
				int kc = Calculaotr_distance.kc_giua_hai_node(j, matrix,
						Monitor.get(i));
				// Giới hạn khoảng cách nhỏ hơn bằng gioi_han_kc luôn, MDGIP
				if (kc > -1 && kc < gioi_han_kc) {
					Sm[Monitor.get(i)][index] = j;
					index++;
				}
			}
		}
		System.out.println("Khởi tạo Sm xong");
		int c = 0;
		do {
			c++;
			System.err.println(" c: " + c);
			/**
			 * Xác định tần suất xuất hiện của tất cả các node trong các tập Sm
			 */
			int frequence[] = new int[size];
			for (int i = 0; i < size; i++) {
				// xác định số lần xuất hiện của i trong Sm
				int count = 0;
				for (int a = 0; a < Monitor.size(); a++) {
					for (int b = 0; b < size; b++) {
						if (Sm[Monitor.get(a)][b] == i) {
							count++;
						}
					}
				}
				frequence[i] = count;
			}
			// xác định node có giá trị lớn nhất trong frequence
			int nodeMax = 0;
			for (int i = 0; i < size; i++) {
				if (frequence[i] > -1 && frequence[i] > frequence[nodeMax]) {
					nodeMax = i;
				}
			}
			frequence[nodeMax] = -1;

			C.add(nodeMax);

			List<Integer> remove = new ArrayList<Integer>();
			for (int i = 0; i < Monitor.size(); i++) {
				int kc = Calculaotr_distance.kc_giua_hai_node(nodeMax, matrix,
						Monitor.get(i));
				if (kc > -1 && kc < gioi_han_kc) {
					// thêm m vào Px và loại m khỏi M+
					for (int a = 0; a < size; a++) {
						if (Pm[nodeMax][a] == -1) {
							Pm[nodeMax][a] = M[i];
							break;
						}
					}
					remove.add(Monitor.get(i));
					frequence[Monitor.get(i)] = -1;
				}
			}
			for (int i = 0; i < remove.size(); i++) {
				Monitor.remove(Monitor.indexOf(remove.get(i)));
			}
			remove.clear();
		} while (!Monitor.isEmpty());
		/**
		 * Phần ghi file
		 */
		BufferedWriter bw = null;
		try {
			File file = new File("E:/DATA/tap_C_kc200_k20.txt");
			if (!file.exists()) {
				file.createNewFile();
			}
			FileWriter fw = new FileWriter(file.getAbsoluteFile());
			bw = new BufferedWriter(fw);
			// /////////////////////////////
			for (int i = 0; i < C.size(); i++) {
				bw.write(C.get(i).toString());
				bw.newLine();
			}
		} catch (Exception e) {
			System.err.print("Ex GSSS");
		} finally {
			try {
				bw.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		return C;
	}
}
